#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int n = arr.size();
        vector<int> prefix(n + 1);
        prefix[0] = 0;
        // 构造前缀和
        for(int i = 1; i <= n; i ++) {
            prefix[i] = arr[i - 1] + prefix[i - 1];
        }

        int sum = 0;
        for(int i = 1; i <= n; i += 2) {
            for(int j = 0; j < n - i + 1; j ++) {
                // 使用前缀和
                sum += prefix[j + i] - prefix[j];
            }
        }
        return sum;
    }
};

int main() {
    Solution solution;
    vector<int> arr = {1, 4, 2, 5, 3};
    int result = solution.sumOddLengthSubarrays(arr);
    cout << "The sum of all odd length subarrays is: " << result << endl;
    return 0;
}
